\chapter{绪论}

\section{研究背景及意义}
自从我国80年代改革开放起，工业发展的速度就非常的迅速且稳定。
回顾近代工业史，我国在制造业方面的成就尤为亮眼，无论是工业化的科技理论水平还是实际成果产业都在世界舞台上有着令人瞩目的表现。
从官方数据总结中我们可以清晰的发现，在2017年我国GDP的构成中，有近乎三分之一的数据量来源自工业经济。从全球化的角度去对比，
通过当前世界工业标准分类我们可以清晰的发现，我国在22个总体大类中的煤炭，生铁等等七个传统大类中稳居制造生产的榜首，甚至在某些类别中具有压倒性地位；
同时针对于互联网时代下的新工业制造，我国也依旧具有很先进的科技手段和成熟的发展模式，
例如无论是工业机器人还是当今有着非常广泛应用的新能源汽车，我国都具有极高的市场占有率，并呈现出非常强劲的长期竞争力。
但是这并不代表着我国的工业发展是完美的，没有任何问题的。
我国工业前期的迅猛发展离不开人口红利和优势，仔细分析还会发现整体工业发展不平衡，
虽然科技理论非常先进，但是很多传统的工业流水线并不能利用被他们认为成“空中楼阁”的相关科学理论，
而是滞后的一直利用劳动力的廉价和数量的巨大进行重复的作业。这一现状随着整体人口结构的转型可预见的将会暴露越来越多的问题\cite{郭朝先2018改革开放40年中国工业发展主要成就与基本经验}。

传统的工业制造不再能满足21世纪以来新的产品需求：我们需要更加短的生产周期和更加复杂的产品性质，同时也不能忽略更加灵活的产品更新需求。
在这一现状的催生下，一个非常有创造性的理论被提出并逐渐完善应用。那就是柔性制造系统(Flexible Manufacturing System, FMS)。
这一系统着眼于现代工业对于多样和更新的需求，具有优秀的柔性化和智能化性质。
典型的FMS需要几个基本模块：数控机床，物料传递系统，计算机总控系统。
由于其集成性和网络化的特点，它为企业提供了更加高效、灵活的制造方式,从而提高了企业的竞争力。
较为典型的是它在生产时针对共享资源的处理，在实际工业生产中为相关的产线提供了极大的效率提升；
在无论是针对产品更新度还是多样化，柔性制造系统都为现代工业交出了一份令人惊艳的答卷\cite{李诚2015基于Petri网和启发式搜索的调度算法研究}\cite{金炳娥2010基于Petri网的柔性制造系统调度问题的研究}。
而在柔性制造系统中，有一个模块发挥着非常关键的作用，这一模块就是生产调度。这一模块的质量和效率直接关系到整体生产的质量和效率，无论从经济角度还是社会层面都具有非常战略性的意义。
但是这一问题经常是难以找到非常好的方式进行解决的：因为极其大量的实际产线调度问题都是多项式复杂程度的非确定性问题，
在学术界我们称之为NP(Non-deterministicPolynomial)完全问题\cite{李诚2015基于Petri网和启发式搜索的调度算法研究}\cite{李昭智1984NP-完全问题浅谈}，
这一特点使得想要找到一个明确固定的规律是完全不可能的，从而导致了整体制造的调度非常的复杂。不止如此，随着工业发展，对于某些特定的产品，整体产线需要很多约束条件，
例如精确的时间要求，极端的生产环境等。这一实际情况无疑又加大了生产调度问题寻求更优方法的难度。综上我们不难发现，学术界和企业界都对调度问题有着非常大的关注度。

在新工业中，电子工业无疑是非常重要的一个方向。由于大多数电子组件的化学成分都为硅或部分含硅化合物，我们习惯性的直接将电子产业等同于半导体产业。
半导体产业与我们现代的生活息息相关，其中集成电路技术几乎出现在先进可以看到的所有电子产品中。
从大家每天使用的手机到机构企业需要的大型计算机，都不能离开集成电路，这也代表着半导体产业的强应用性。而在整体半导体产业中，对半导体的加工无疑是最具有经济效益和社会意义的产业。
具体对其进行分类，当今我国应用的主要技术包括晶圆制造加工，薄膜沉积、光刻、蚀刻、掺杂等等。
其中，晶圆制造这一步骤主要通过化学手段将硅精纯并制作成硅片达成；而晶圆加工往往需要更多的工业控制生产步骤加入，通过包括融化、晶体成长、裁切检测、切片清洗等等复杂而精确的加工步骤产生出最终的芯片。

想要解决晶圆制造问题，第一步就需要对一个现实复杂的模型进行精确又高效的建模。
只有数学模型贴合性好，我们才能正确的进行算法的模拟和运算，从而适应不同的加工需求和给出更优秀的调度结果。
一般在学术研究中，我们常用Petri网、自动机等对柔性制造系统进行建模分析；自动机无法很好的表述出系统并发关系，使针对晶圆制造这一典型的复杂离散系统，我们选择petri网进行建模\cite{顾佳颖2018考虑多重约束的半导体晶圆制造系统调度方法}\cite{贾林林2017半导体晶圆制造系统的瓶颈管理及调度优化研究}\cite{朱雪初，乔非2017基于工业大数据的晶圆制造系统加工周期预测方法}\cite{吴立辉，张洁2009基于多代理的知识有色赋时Petri网的晶圆制造系统建模方法}。

\section{国内外研究现状}
1962年，CarlAdam Petri在他的博士论文《与自动机通信》中首次提出了Petri网的概念。
后来，该模型被命名为Petri网，逐渐成为了理论计算机科学中的一个很有创造性的方向。
由于当时自动机理论中缺乏重要的并发概念，不适合描述和研究狭义相对论、测不准原理等现代物理学中的典型问题，
而Petri网模型能以自然、直观、易懂的方式分析并行系统的各种状态行为，这一非常优异的理论特色使得相关学术界中很多研究人员产生了浓厚的兴趣\cite{me2017}\cite{Martinez1986}。

1975年7月，麻省理工学院举办了第一届Petri网及相关理论研讨会。此后，国际上每年都会定期举办有关Petri网相关理论的研讨会，关于Petri网相关理论及其应用的研究成果不断涌现。
经过多年的深入研究，Petri网理论在垂直和水平两个方向上都得到了很大的发展和完善。
垂直发展体现在Petri网的建模理论上，从最基本的条件/事件网(C/E)、位置/过渡网(P/T)逐渐发展到谓词/过渡网和彩色网等高级网。
横向发展体现在Petri网的时间属性上，从非参数网发展到时间Petri网和随机Petri网。
目前，Petri网理论已广泛应用于柔性制造系统、离散事件系统、故障诊断系统、工作流建模与管理等多个领域\cite{5715371}\cite{vanderAalst2000}\cite{Clempner+2014+931+939}。

国内对于petri网的研究也在近30年中不断进步和完善。
1988年，南京航空航天大学的陈浩发表了第一篇关于Petri网的硕士论文，而随着国内学术界的不断耕耘和发展，相关的论文和成果达到近5000篇。
目前，仍有大量研究人员在该领域不断进行更深入的探索，相信未来会发现更多有用的研究成果。


\section{论文结构}
本文主要是研究基于Petri网和蚁群算法的柔性制造系统的调度问题，
基于库所时间网与变迁时间网提出一种新的时间网子类，
并使用此时间网子类对实际制造系统进行建模，
最后使用蚁群算法求解模型调度策略，
并结合模型实际情况，对蚁群算法设计了6种优化方案。
本论文包含五章，各章节主要内容如下：

第一章概括性地阐述了本文研究的背景与意义，简述了Petri网、各调度算法在国内外的现阶段的研究情况，然后总结了一系列求解调度问题的方法，最后给出了本文的组织结构。

第二章是本文的基础知识部分，这部分主要是详细介绍了Petri网的基本理论，包过Petri网的基本概念、定义和特性等，然后介绍了Petri网在晶圆制造领域的一些应用
并且介绍了基于Petri网的FMS建模相关理论与方法，通过一个简单的例子，简述了Petri网建模的过程。
最后介绍了一系列时间网。

第三章在第二章的基础上，将变迁时间网与库所时间网进行结合，提出变迁库所时间网这种新的时间网子类。
并基于变迁库所时间网设计了一种供调度算法使用的变迁发射流程，
并设计了一种用于计算各种Petri网模型调度策略的程序架构。
并通过一个简单的例子，描述了此发射流程的全过程。
在此基础上，使用变迁库所时间网对一个实际的晶圆制造系统进行建模。

第四章设计并使用蚁群算法对第四章建立的变迁库所时间网模型求解调度策略。
并对求解出的调度策略进行分析，对蚁群算法提出了一系列优化方案。
最后分别对这些优化方案进行实验分析。

最后一章为总结与展望，对本文所研究的内容进行了回顾，并提出了研究存在的不足以及接下来需要进一步研究的地方。